1
Anatomy of the Linked List
AI019 Lesson 4
00:00

At its fundamental level, a linked list is a recursive data structure defined by its own absence or its composition. A list is either empty (represented as []) or it consists of a Head containing a single value and a Tail which is itself a complete list.

1. The Recursive Definition

By defining the tail as "itself a list," we allow for infinite nesting. This is illustrated by the construction of [ 1 | [ 2 | [ 3 | [ ] ] ] ], where each pipe operator (|) separates the immediate value from the remaining structure.

12[]HeadTail (is a list)

2. Primitive vs. Abstraction

Primitive lists in the Erlang VM (BEAM) are simple structures. Behaviors like List.flatten/1 are abstractions provided by Elixir's List module. The raw data structure does not "know" how to flatten itself; the module provides the logic to traverse the nested heads and tails.

3. The "Nesting Doll" Analogy

Think of a Linked List like a set of Russian Nesting Dolls. The outermost doll is the Head. When you open it, you find exactly one thing: another doll (the Tail). You only reach the Empty state when you open the final, smallest doll and find nothing inside.

main.py
TERMINAL bash — 80x24
> Ready. Click "Run" to execute.
>